package com.yc.baseapi;

import java.util.*;

/**
 * 栈(stack)
 */
public class TestStack {

    public static void main(String[] args) {
        TestStack t = new TestStack();
//        t.m1();
//        t.m2();
//        t.m3();
        t.m4();
    }

    public void m1() {
        Stack<String> s = new Stack();
        s.push("a");
        s.push("b");
        s.push("c");

        System.out.println(s.peek());
        System.out.println(s.peek());

        while (!s.empty()) {
            System.out.println(s.pop());
        }
    }

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     */
    public void m2() {
//        String t = "()";
//        String t = "()[]{}";
//        String t = "[";
//        String t = "((";
//        String t = ")";
        String t = "([)]";
        System.out.println(m2_isValid_3(t));

    }

    public boolean m2_isValid(String s) {
        //定义一个字符栈
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c=='(' || c=='[' || c=='{') {//如果是左括号：入栈
                stack.push(c);
            } else {//否则：和出栈的字符做比较，看是否是一对
                if (!stack.empty()) {
                    char p = stack.pop();
                    if (!((p == '(' && c == ')') || (p == '[' && c == ']') || (p == '{' && c == '}'))) {
                        return false;
                    }
                } else {
                    return false;
                }

            }
        }
        
        return stack.empty();
    }

    public boolean m2_isValid_1(String s) {
        Map<Character, Character> m = new HashMap<>();
        m.put('(', ')');
        m.put('[', ']');
        m.put('{', '}');

        //定义一个字符栈
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (!stack.empty() && c == m.get(stack.peek())) {//能出栈就出栈，否则就入栈
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        return stack.empty();
    }

    /**
     * 这个效果第二（占用空间比m2_isValid大一点点），
     * 但提供了一个toCharArray的方法
     * 经过实验：把toCharArray替换成s.charAt(i)占用空间更小
     * @param s
     * @return
     */
    public boolean m2_isValid_2(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                        (c == ']' && top != '[') ||
                        (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    /**
     * 试图把性能推到极致：栈都不用，直接用LinkedList
     * 预想：Stack在pop时，本质是重新生成了一个数组，感觉比较浪费空间。所以优化成链表。
     * 实际结果：内存占用更高了。可能是链表结构复杂的原因
     * @param s
     * @return
     */
    public boolean m2_isValid_3(String s) {
        LinkedList<Character> cs = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                cs.add(c);
            } else {
                if (cs.isEmpty()) return false;
                char top = cs.removeLast();
                if ((c == ')' && top != '(') ||
                        (c == ']' && top != '[') ||
                        (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return cs.isEmpty();
    }

    /**
     * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
     *
     * 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
     */
    public void m3() {
//        String s = "1 + 1";
//        String s = " 2-1 + 2 ";
        String s = "-(-1-2)";
//        String s = " (1+(4+5+2)-3)+(6+8)";
//        String s = "2147483647";
//        String s = "1-(     -2)";
//        String s = "- (3 + (4 + 5))";
//        String s = "1-11";
//        String s = "-(-2)+4";
        System.out.println(calculate2(s));
    }

    public int calculate(String s) {
        Stack<String> stack = new Stack<>();

        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                continue;
            }
            if (c == '(' || c == '+' || c== '-') {//入栈
                stack.push(c+"");
                continue;
            }
            if (c == ')') {//右边括号左边一定是一个数字数字，不可能是左括号，否则就是错误公式
                String p = stack.pop();
                stack.pop();//把左括号出栈

                int b = Integer.parseInt(p);//得出的结果先不入栈：继续往前尝试计算

                //再往上判断一层
                js(stack,b);
                continue;
            }
            //此时c必然就是数字了：往后继续遍历直到不是数字为止，然后修改i值
            String cs = c + "";
            while(i < s.length()-1) {
                i++;
                char nc = s.charAt(i);
                if (nc >= '0' && nc <= '9') {
                    cs += nc;
                } else {
                    i--;
                    break;
                }
            }

            if (stack.empty()) {//栈为空，数字入栈
                stack.push(cs);
                continue;
            }

            String p = stack.peek();//栈顶元素:上一个字符

            if (p.equals("(")) {
                stack.push(cs);
                continue;
            }

            if (p.equals("+") || p.equals("-")) {//上一个字符是运算符
                stack.pop();//运算符+ 出栈
                if (p.equals("-") && (stack.empty()||stack.peek().equals("("))) {//没有了，说明就是个负数
                    stack.push("-"+cs);//cs是纯数字字符串，不可能有负号
                    continue;
                }
                int a = Integer.parseInt(stack.pop());//第一个运算数字出栈（+的特点，上一个必然是数字，而且不空）
                int b = Integer.parseInt(cs);//第二个运算数字

                b = (p.equals("+"))?(a+b):(a-b);//结果先不入栈，继续尝试往前计算

                //再往上判断一层
                js(stack,b);
//                continue;
            }

        }

        //从最后的栈内返回结果
        String p = stack.pop();
        if (!stack.empty() && stack.pop().equals("-")) {
            if (p.charAt(0) == '-') {//负数前面有个负号
                return Integer.parseInt(p.substring(1));
            } else {
                return Integer.parseInt("-" + p);
            }
        } else {
            return Integer.parseInt(p);
        }

    }

    /**
     * 往上继续计算
     * @param stack
     * @param b 出栈的计算出来的值
     */
    public void js(Stack<String> stack, int b) {
        if (stack.empty()) {//栈为空，直接入栈
            stack.push(b+"");
        }
        //再往上判断一层
        String p = stack.peek();
        if (p.equals("+") || p.equals("-")) {//栈顶是运算符：计算并入栈（由于是从左到右贪心计算，所以再往前就不可能还有需要计算的）
            stack.pop();//运算符+ 出栈
            if (p.equals("-") && (stack.empty()||stack.peek().equals("("))) {//没有了，说明就是个负数
                stack.push((0-b)+"");
                return;
            }
            int a = Integer.parseInt(stack.pop());
            stack.push(((p.equals("+"))?(a+b):(a-b))+"");//把运算值入栈
        } else {//否则，直接把结果入栈
            stack.push(b+"");
        }
    }

    /**
     * 标准版
     * @param s
     * @return
     */
    public int calculate2(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        // sign 代表正负
        int sign = 1, res = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                int cur = ch - '0';
                while (i + 1 < length && Character.isDigit(s.charAt(i + 1)))
                    cur = cur * 10 + s.charAt(++i) - '0';
                res = res + sign * cur;
            } else if (ch == '+') {
                sign = 1;
            } else if (ch == '-') {
                sign = -1;
            } else if (ch == '(') {
                stack.push(res);
                res = 0;
                stack.push(sign);
                sign = 1;
            } else if (ch == ')') {
                res = stack.pop() * res + stack.pop();
            }
        }
        return res;
    }

    public void m4() {
//        String[] a = {"2","1","+","3","*"};
//        String[] a = {"4","13","5","/","+"};
        String[] a = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
        System.out.println(evalRPN(a));

    }

    /**
     * 逆波兰式
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (int i=0; i<tokens.length; i++) {
            String cs = tokens[i];
            if (Character.isDigit(cs.charAt(cs.length()-1))) {//数字：入栈
                stack.push(Integer.parseInt(cs));
            } else {//运算符：直接运算，然后入栈
                int r = stack.pop();
                if ("+".equals(cs)) {
                    r = stack.pop() + r;
                } else if ("-".equals(cs)) {
                    r = stack.pop() - r;
                } else if ("*".equals(cs)) {
                    r = stack.pop() * r;
                } else if ("/".equals(cs)) {
                    r = stack.pop() / r;
                }
                stack.push(r);
            }
        }

        return stack.pop();
    }

}
